// 5种解法：
// 1.暴力解法：递归 O(2^n)
// 2.尾调递归：优化时间和空间
// 3.动态规划：数组 备忘录  
// 4.动态规划：数组 状态压缩 ，3个变量
// 5.数学公式，
// 6.

// 斐波那 ，O(2^n)
function fibonacci(n){
    //方法1 递归方式
    if(n<=1){
        return n;
    }
    return fibonacci(n-1)+fibonacci(n-2);

}

// 动态规划:空间采用数组,自下而上
function fibonacci1(n){
    //方法2 循环方式
    let arr=[0,1];
    for (let index = 2; index < n; index++) {
       
        arr[index]=arr[index-2]+arr[index-1]
    }
    return arr[n]
}
// 动态规划:空间采用数字变量，自下而上(数组方式)
function fibonacci2(n){
    //方法2 通过2个变量来把前两个的值保存起来，
    // 因为我们知道1 和 2 的值 一定为1，
    // 从2开始，每次都把前两个相加
    // 把前两个重新赋值
    if(n<=1){
        return 1;
    }
    let first=1;//fn-2
    let second=1;//fn-1
    let res=2;
    for (let index = 2; index <= n; index++) {
        res=first+second;
        first=second;
        second=res;
    }
    return res
}


// 通过对象缓存方式，通过空间换取速度，会产生很多多余的空间，可以继续优化
function fibonacci3(n,cache){
    //方法1 递归方式
    if(n<=1){
        return 1;
    }else if(n in cache){
        return cache[n]
    }else{
        // 把之前的结果保存到缓存对象里
        cache[n]=fibonacci3(n-1,cache)+fibonacci3(n-2,cache);
        return cache[n]
    } 
}

// 尾递归，优化了时间复杂度为O(n)
function fibonacci4(n,a=0,b=1){
    console.log('n',n,a,b)
    if(n===0){
        return 0;
    }
    if(n===1){
        return b;
    }
    return fibonacci4(n-1,b,a+b)

}

function fib(n, prev = 0, next = 1) {
    console.log(n,prev,next)
    if (n === 0) { return next; }
    return fib(n - 1, next, prev + next);
}
    

// 通过数学公式
function fibonacci5(n) {
    const c = Math.sqrt(5);
    return Number((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
}
// console.log(window,globalThis)
 // console.log(process)

// calcTime('fibonacci',function(){fibonacci(30)})
// calcTime('fibonacci1',function(){fibonacci1(30)})
// calcTime('fibonacci2',function(){fibonacci2(30,{})})
// calcTime('fibonacci3',function(){ return fibonacci3(5,{})})
// calcTime('fibonacci4',function(){ return fibonacci11(5)})
// calcTime('fib',function(){ return fib(5)})
calcTime('fibonacci4',function(){ return fibonacci4(5)})
//
function calcTime(label,fun){
    console.time(label)
    console.log('结果',fun());
    console.timeEnd(label)
}

function calcTime2(tag,fun){
    let start=new Date().getTime();
    fun()
    console.log(new Date().getTime(),new Date().getTime()-start)
}